
// 题目链接：https://leetcode.com/problems/intersection-of-two-arrays-ii/

/**
 * Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

Example 3:

Input: nums1 = [1,2,2,1], nums2 = [2]
Output: [2]
 */

/**
 * 算法解题分析
 * 不可行：可能求交集会首先考虑使用 Set 数据结构，但是因为集合有可能是重复的值，所以不可行
 * 解题方法：
 * 方法1：遍历 nums1 数组，用一个对象存储数据的值作为 key, 出现次数作为 value，构成映射关联。再遍历 nums2，
 * 出现在 map 上将它添加到输出数组的交集中，并且 map 上对应的次数减1，如果等于1则删除该属性，时间复杂度 O(n), 空间复杂度 O(1)
 * 方法2: 使用 Map 数据结构, 实现思路一样
 * 方法3: 遍历数组 nums1, 如果存在另一个数组，塞进集合中，然后将它从另一个数组中删除
 * 总结：使用 Map 数据结构性能更好些
 */

// 方法1：暴力破解法 - 遍历
function intersect (nums1, nums2) {
  const map = {}

  nums1.forEach(num => {
    if (map[num]) {
      map[num] += 1
    } else {
      map[num] = 1
    }
  })

  const insert = []

  nums2.forEach(num1 => {
    if (map[num1]) {
      if (map[num1] > 1) {
        map[num1] -= 1
      } else {
        Reflect.deleteProperty(map, num1)
      }

      insert.push(num1)
    }
  })

  return insert
}

// 代码优化
function intersect1 (nums1, nums2) {
  const map = {}

  nums1.forEach(num => {
    map[num] = map[num] ? map[num] + 1 : 1
  })

  const insert = []

  nums2.forEach(num1 => {
    if (map[num1]) {
      insert.push(num1)
      --map[num1]
    }
  })

  return insert
}

// 优化方法，使用map 和 filter 函数
function intersect2 (nums1, nums2) {
  const map = {}

  nums1.map(item => {
    map[item] ? ++map[item] : map[item] = 1
  })

  return nums2.filter(item => {
    return map[item] ? map[item]-- : false
  })
}

// 方法2: 使用 Map 数据结构
function intersectByMap (nums1, nums2) {
  const map = new Map()

  nums1.forEach(num => {
    if (map.has(num)) {
      map.set(num, map.get(num) + 1)
    } else {
      map.set(num, 1)
    }
  })

  const insert = []

  nums2.forEach(num1 => {
    const temp = map.get(num1)

    if (temp) {
      if (temp > 1) {
        map.set(num1, temp - 1)
      } else {
        map.delete(num1)
      }

      insert.push(num1)
    }
  })

  return insert
}

// 方法3: 使用splice

function intersectBySplice (nums1, nums2) {
  const insert = []

  nums1.map(num => {
    const index = nums2.indexOf(num)

    if (index !== -1) {
      insert.push(num)
      nums2.splice(index, 1)
    }
  })
  console.log(insert)

  return insert
}

// What if the这 given array is already sorted? How would you optimize your algorithm?
// 进阶1: 怎么输出有序的集合
// 解法1: 两个数组，交集有序输出。使用双指针，数组两两比较，较小的数指针往下移动一位，直到有一个数组遍历完，结束循环
// 解法2: 用数组遍历和 splice 删除

// 方法1：使用双指针
function intersectTwo (nums1, nums2) {
  const len1 = nums1.length
  const len2 = nums2.length

  nums1 = sortArr(nums1)
  nums2 = sortArr(nums2)

  let i = 0
  let j = 0
  const insert = []

  while (i < len1 && j < len2) {
    if (nums1[i] < nums2[j]) {
      ++i
    } else if (nums1[i] > nums2[j]) {
      ++j
    } else {
      insert.push(nums1[i])
      ++i
      ++j
    }
  }

  return insert
}

function sortArr (arr) {
  return [...arr].sort((a, b) => a - b)
}

function intersect3 (nums1, nums2) {
  nums1.sort((a, b) => a - b)
  nums2.sort((a, b) => a - b)

  const insert = []
  let i = nums1.length - 1
  let j = nums2.length - 1

  while (nums1[i] > nums2[0] && (i > 0 && j > 0)) {
    if (nums1[i] > nums2[j]) {
      --i
    } else if (nums1[i] < nums2[j]) {
      --j
    } else {
      insert.push(nums1[i])
      --i
      --j
    }
  }

  return insert
}

// What if elements of nums2 are stored on disk, and the memory is limited such
// that you cannot load all elements into the memory at once?

// 更小的内存空间

function intersect4 (nums1, nums2) {
  nums1.sort((a, b) => a - b)
  nums2.sort((a, b) => a - b)

  const result = []

  while (nums1.length && nums2.length) {
    if (nums1[0] === nums2[0]) {
      result.push(nums1.shift())
      nums2.shift()
    } else if (nums1[0] < nums2[0]) {
      nums1.shift()
    } else {
      nums2.shift()
    }
  }

  return result
}

// const nums1 = [1, 2, 2, 2, 2, 3, 3, 3, 1, 3]
// const nums2 = [2, 3]

// intersect(nums1, nums2)
// intersectByMap(nums1, nums2)

module.exports = {
  intersect,
  intersect1,
  intersect2,
  intersectByMap,
  intersectBySplice,
  intersectTwo,
  intersect3,
  intersect4
}
